#include "BTreeNode.h"
using namespace std;



/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer);
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	// Traverse the leaves until we hit the end or 
	// until we hit a pid that is -1, which is our sentinel. 
	for (int i = 0; i < BUF_SIZE - 1; ++i)
	{
		if (buffer[i].ri.pid == -1)
		{
			return i;
		}
	}

	// This means that we traversed the entire node but we 
	// didn't hit any sentinels. Therefore, we have 
	// BUF_SIZE - 1 keys--the max keys. 
	return BUF_SIZE - 1;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 

	if (getKeyCount() == BUF_SIZE-1)
	{
		return -1;
	} 

	int eid;
	locate(key, eid);

	/*
	 * Start shifting one to the left from BUF_SIZE -2
	 * which is the last PageId that points to a RecordFile. 
	 */

	for (int i = BUF_SIZE-2; i > eid; i--)
	{
		buffer[i] = buffer[i-1];
	}



	// insert pair
	buffer[eid].ri = rid; 
	buffer[eid].key = key;

	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
		BTLeafNode& sibling, int& siblingKey)
{ 

	if (sibling.getKeyCount() != 0)
	{
		return -1;
	}

	int keys = BUF_SIZE-1;

	// enforces right-heavy (ty integer division)
	int midKey = (keys+1)/2;

	int ptr = getNextNodePtr();
	int eid;
	if (locate(key, eid) != 0) eid = BUF_SIZE-1;
    for (int i = BUF_SIZE-1; i > eid; i--) buffer[i] = buffer[i-1];
	buffer[eid].key = key;
	buffer[eid].ri = rid;
	// move half of the buffer to sibling and clear the memory
	for (int i = 0; i < BUF_SIZE - midKey; i++)
	{
		sibling.buffer[i] = buffer[i+midKey];
		buffer[i+midKey].ri.pid = -1;
	}


	siblingKey = sibling.buffer[0].key;
	sibling.setNextNodePtr(ptr);
	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int numKeys = getKeyCount(); 

	for (int i = 0; i < numKeys; ++i)
	{
		if (buffer[i].ri.pid == -1) return -1;
		if (buffer[i].key >= searchKey) 
		{
			eid = i;
			return 0;
		}
	}

	// did not find searchKey in node.  
	if (numKeys == BUF_SIZE - 1)
	{
		return -1; 
	}

	// When creating a node, set eid = 0 and return. 
	if (numKeys == 0)
	{
		eid = 0;
		return 0;
	}

	// Otherwise, return eid at the end of the wel-formed section of the buffer. Everything else 
	// is garbage.
	eid = numKeys;
	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	if (eid < 0 || eid >= BUF_SIZE-1)
		return -1;

	key = buffer[eid].key;
	rid = buffer[eid].ri;
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	// buffer[BUF_SIZE-1] contains the pid to the sibling node. 
	return buffer[BUF_SIZE-1].ri.pid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	// Can't have negative page id's!
	if (pid < -1)
	{
		return -1;
	}

	buffer[BUF_SIZE-1].ri.pid = pid;
	return 0; 
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer);
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
    if (buffer[0].pi == -1) return 0;
	for (int i = 0; i < BUF_SIZE; ++i)
	{
		if (buffer[i].pi == -1)
		{
			/*
			 * we return (i-1) as opposed to (i) because there is a valid pointer following the 
			 * last key for non leaf nodes. 
			 */
			return i-1;
		}
	}

	return BUF_SIZE-1;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int numKeys = getKeyCount(); 
	// All nodes are full (minus the dummy). Therefore, we must
	// insertAndSplit. 
	if (numKeys == BUF_SIZE-1)
	{
		return -1;
	}

	int eid = numKeys;
	// locate where to insert pair, if not found insert at numKeys
	for (int i = 0; i < numKeys; i++)
	{
		if (buffer[i].key >= key)
		{
			eid = i;
			break;
		}
	}

	// shift memory of array after eid
	for (int i = BUF_SIZE-1; i > eid; i--)
	{
		buffer[i] = buffer[i-1];
	}

	// insert pair
	buffer[eid+1].pi = pid; 
	buffer[eid].key = key;

	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	if (sibling.getKeyCount() != 0)
	{
		return -1;
	}


    Entry temp[BUF_SIZE+1];
    int i;
    for (i = 0; i < BUF_SIZE-1 && buffer[i].key < key; ++i) temp[i] = buffer[i];
    temp[i].pi = buffer[i].pi; temp[i].key = key;
    temp[i+1].pi = pid; temp[i+1].key = buffer[i].key;
    for (++i; i < BUF_SIZE; ++i) temp[i+1] = buffer[i];
	int keys = BUF_SIZE-1;

	// enforces right-heavy (ty integer division)
	int mKey = keys/2;
	midKey = temp[mKey].key;

	// move half of the buffer to sibling and clear the memory
    int length = BUF_SIZE - mKey;
	for (int i = 0; i < length; i++)
	{
		sibling.buffer[i] = temp[i+mKey+1];
	}
	for (i = 0; i < mKey+1; i++) buffer[i] = temp[i];
    for (; i < BUF_SIZE; i++) buffer[i].pi = -1;

	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int numKeys = getKeyCount(); 

	if (numKeys == 0)
	{
		return -1;
	}

	for (int i = 0; i < numKeys; i++)
	{
		if (buffer[i].key > searchKey)
		{
			pid = buffer[i].pi;

			return 0;
		}
	}

	// when full
	pid = buffer[numKeys].pi;

	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	buffer[0].pi = pid1;
	buffer[0].key = key;
	buffer[1].pi = pid2;

	return 0; 
}


